โครงสร้างเชิงวนซ้ำของตรรกะ
เพื่อสร้างสมองดิจิทัลที่ซับซ้อน เราต้องกำหนดไวยากรณ์ของภาษาที่พวกเขาใช้ก่อน ในพีชคณิตบูลีนใด ๆ $(S, +, \cdot, ', 0, 1)$ เราจะนิยาม นิพจน์บูลีน บนเซตของตัวแปร $x_1, \dots, x_n$ ผ่านกระบวนการเหนี่ยวนำเชิงโครงสร้าง:
1. ค่าคงที่ใด ๆ $s \in S$ เป็นนิพจน์บูลีน
2. ตัวแปรใด ๆ $x_1, \dots, x_n$ เป็นนิพจน์บูลีน
หาก $X_1$ และ $X_2$ เป็นนิพจน์บูลีนแล้ว ดังนั้นนิพจน์ต่อไปนี้ก็เป็นนิพจน์ที่ถูกต้องเช่นกัน:
$(X_1), \quad X_1', \quad X_1 + X_2, \quad X_1 \cdot X_2$
ลำดับความสำคัญและความมีประสิทธิภาพ
เมื่อไม่มีวงเล็บ เราจะใช้ลำดับความสำคัญอย่างเคร่งครัดเพื่อหลีกเลี่ยงความคลุมเครือ: การเชื่อม (ค่าจริงเมื่อทั้งสองตัวแปรเป็นจริง) ($\\land$) มีลำดับความสำคัญสูงกว่า การรวม (ค่าจริงเมื่ออย่างน้อยหนึ่งตัวแปรเป็นจริง) ($\\lor$). นอกจากนี้ เพื่อให้การออกแบบฮาร์ดแวร์มีประสิทธิภาพมากขึ้น เราจะใช้ ประตูแบบมี $n$ ขาเข้า. แทนที่จะเชื่อมประตู 2 ขาเข้าหลายตัวต่อกัน เราจะแสดง $a_1 \vee a_2 \vee \dots \vee a_n$ เป็นหน่วยตรรกะเดียว ซึ่งช่วยลดเวลาการแพร่กระจาย (propagation delay) และทำให้โครงสร้างของวงจรง่ายขึ้น
หลักการสะท้อนโครงสร้าง
นิพจน์ทางพีชคณิตทุกตัวคือแผนผังสำหรับวงจรทางกายภาพ พิจารณาการติดตั้งสำหรับ $(x_1 \wedge (\neg x_2 \vee x_3)) \vee x_2$:
- ชั้นภายใน: เราต้องแยก $(\neg x_2 \vee x_3)$ ออกโดยใช้ประตู NOT และประตู OR
- ชั้นกลาง: ผลลัพธ์ถูกส่งเข้าไปยังประตู AND พร้อมกับสัญญาณจาก $x_1$
- ชั้นภายนอก: ในที่สุด สัญญาณจากประตู AND และเส้น $x_2$ ต้นฉบับจะมาบรรจบกันที่ประตู OR สุดท้าย